#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

vector<int> getMax(int num[], int size, int k)
{
    vector<int> ans;
    deque<int> dq;
    
    for (int i = 0; i < k; i++) {
        while(!dq.empty() && num[i] >= num[dq.back()])
	    dq.pop_back();
	dq.push_back(i);
    }

    for (int i = k; i < size; i++) {
	ans.push_back(num[dq.front()]);
        while(!dq.empty() && num[i] >= num[dq.back()])
	    dq.pop_back();
	while(!dq.empty() && dq.front() <= i-k)
	   dq.pop_front(); 
	dq.push_back(i);
    }
    ans.push_back(num[dq.front()]);
    return ans;
}


int main(int argc, char **argv)
{
    int a[] = {3, 4, 5, 7, 3, 5, 2, 9 };
    vector<int> ans = getMax(a, sizeof(a)/sizeof(int), 3);
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
    cout << endl;
}
